資料結構

過了些時日，我們終於來到了樹狀結構的地方，樹狀結構是演算法題目中的一個大篇幅，也是相對前面陣列、佇列來說結構更加複雜的地方。
今天我們先大概了解一下樹狀結構的定義，我們會首先專注在其中一種樹狀結構，也是大多題目普遍會使用的樹狀結構 - 二元樹，這篇與後面的幾篇會來透過題目展示一下關於樹的特性。

首先，我們借用一下維基百科對樹這種結構的定義：
由 n (n > 0) 個有限節點組成，一個具有層次關係的集合。
這樣的結構被稱呼為樹，因為就像是一棵倒過來、倒掛的樹。

• 層次關係裡，在上方的稱作父節點，下方稱作子節點。
• 樹裡面最上面那顆、沒有任何父節點的節點稱作根節點。
• 沒有任何子節點的節點稱做葉節點
• 除了根節點以外，每個節點都有且只有一個父節點
• 除了根節點以外，所有子節點都可以分成多個不相交的另一棵樹(即把該子節點視為另一棵樹的根節點的話)
• 樹狀結構不存在環(Cycle)

   1
 /   \
2     3

這樣的結構裡，1 是根節點，2 是 1 的子節點，1 是 2 的父節點，而 2 和 3 都是葉節點。

上面這些大多是來自 Wiki 對於這個結構的定義，因為樹是比較複雜的結構，我這邊用公定的說明來把它展開，會是一個比較好的入門。
一般的演算法考題，不太用內建類別作為樹結構，而是直接寫一個類別出來。
二元樹就是指每個節點最多能有兩個子節點，以二元樹為例，C# 一般我們會看到這樣去實現：

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
}

二元樹在解題中多為兩種二元樹：

• 滿二元樹(Full Binaray Tree)
  除了葉節點以外，所有節點均有兩個子節點
• 完全二元樹(Complete Binary Tree)
  除了最後一層以外，所有節點均有兩個子節點，且最後一層所有子節點集中在左方
  滿二元樹一定是完全二元樹，完全二元樹不一定是滿二元素。
  這邊稍微帶過名詞，有點印象就可以。

遍歷二元樹

二元樹要聊的話無可避免的就是要知道該怎麼用各種順序去遍歷這棵樹。
相較以往線性結構的遍歷，二元樹總共有三種遍歷方式：前序、中序、後序。
以下面這棵樹為例

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

前序的走訪順序是：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
中序的走訪順序是：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
後序的走訪順序是：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
這邊這個序的意思是，走訪元素的時候訪問元素的發生時間點。
前序是在走訪到元素的時候直接訪問元素，後序是離開元素的時候訪問元素。
中序則是在二元樹左邊子樹遍歷完後，遍歷右邊子樹前才訪問。
如果簡單看走訪的點的相對順序，
前序是 中 - 左 - 右
中序是 左 - 中 - 右
後序是 左 - 右 - 中

遞回來實做遍歷

遞迴在終止條件明確，重複行動單純的時候，想起來不會太複雜，上面的敘述其實就包含這點。
Leetcode 上有提供三題正好是最基礎的走訪前、中、後序的題目，讓我們套用這個上面的邏輯，來嘗試寫寫前序。

144. Binary Tree Preorder Traversal
這題就很單純，讓你實現前序的遍歷邏輯，會直接給你一棵樹的根結點，要求回傳一個 List，裡面儲存用前序遍歷後的值。

記得前面我們說到，前序的走訪就是進入點後立刻訪問該點，接著左子樹、右子樹的順序。
如果寫成遞迴，終止條件就是不再有左右子樹需要走訪，就會停在該層(有左右子樹，就往下遞迴)。
按照這個邏輯，程式碼如下。

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        var list = new List<int>();
        if(root != null){
            Traverse(root, list);
        }
        return list;
    }

    private void Traverse(TreeNode root, List<int> list){
        list.Add(root.val);
        if(root.left != null){
            Traverse(root.left, list);
        }
        if(root.right != null){
            Traverse(root.right, list);
        }
    }
}

就是很簡單的轉化成程式碼。
我把另外兩題的連結也放上來，但我就不多做說明，直接用程式碼代表。

中序 InOrder
Binary Tree Inorder Traversal

private void Traverse(TreeNode root, List<int> list)
{
    if(root.left != null){
        Traverse(root.left, list);
    }
    list.Add(root.val);
    if(root.right != null){
        Traverse(root.right, list);
    }
}

後序 PostOrder
Binary Tree Postorder Traversal

private void Traverse(TreeNode root, List<int> list)
{
    if(root.left != null){
        Traverse(root.left, list);
    }
    if(root.right != null){
        Traverse(root.right, list);
    }
    list.Add(root.val);
}

主程式碼都一樣，這樣並排在一起，應該可以很清楚的看出這三種序的訪問順序差異，另一個記法就是，一定是先左再右，「O」序就代表中要放在哪個位置，前序就是中左右，中序就是左中右，後序就是左右中。
以上三個訪問順序務必清楚，是處理樹結構相關題目的基本工具。